00100	The boundary should not cross a solid part of the body, i.e.  through
00110	any  scan  segments.    Consider  successive scan segments S1 and S2.
00120	Where there is a cross scan segment Cn which intersects both  S1  and
00130	S2,  the two segments are connected.   S1 and S2 are said to overlap.
00140	The boundary cannot cross the cross segment Cn and  must  turn  back.
00150	Beginning  from one end of S1, the boundary extends through all cross
00160	scans Ci which terminate between S1 and S2,  before  the  first  scan
00170	which intersects both S1 and S2.  See figure 1.
00180	
00190	
00200	
00210	
00220	Boundary linking requires calculating the intersections of segments
00230	from the two crossed scans.  We need calculate only a few of the possible
00240	intersections near the ends of segments.  
00242	Given a segment S1,
00245	we can calculate which cross
00250	scan angles contain segments which intersect S1 (by calculating the angles of endpoints of S1 from
00260	the laser viewpoint, and obtaining cross scans in that range of angles).
00270	The intersection of two segments is determined by making piece_wise
00280	linear approximations to the two segments.  A few minor errors and 
00290	extra effort is caused by slight errors in the intersection process
00300	and by calibration uncertainties which give small angle errors in choosing
00310	cross scans.
     

00100			AI CONFERENCE
00200	
00300	
00400	
00500			STRUCTURED DESCRIPTIONS OF COMPLEX OBJECTS
00600	
00700	
00800	
00900	We describe experiments with symbolic description of curved  objects.
01000	In previous work [Agin] descriptions were generated for the pieces of
01100	objects, according to a volume representation of shape [Binford]. The
01200	pieces  are  an  adequate  description  only of objects with a single
01300	part, like a torus or a snake.   We  have  generalized  and  improved
01400	techniques  for  descriptions  of pieces.  We have also made complete
01500	descriptions which join the scattered pieces into  a  whole.    These
01600	descriptions  are  the  basis for recognition, and a few examples are
01700	discussed.
01800	
01900	The motivations for studying representation of shape are: for  visual
02000	systems  of robots which use depth or image data; for the interactive
02100	programming  of  assembly  robots  for  industrial  tasks;  for   the
02200	computerization    of    industry-machining,    parts    description,
02300	systematization of assembly operations;  for  display;  and  for  its
02400	relevance  to  other  areas  of  AI  and  biology.   Our  concern  is
02500	implementation of symbolic descriptions of shape and space which  are
02600	adequate  for  integrated  robot systems.    We do not think a single
02700	representation is adequate throughout a system, but we have attempted
02800	to  analyze  tasks  in  terms of computational primitives originating
02900	from   topological   and   geometrical   primitives.     and   design
03000	representation  abilities  accordingly.      Representative tasks are
03100	manipulation, display, and recognition.    Manipulation requires mass
03200	and  moments  of  articulated parts, and ability to calculate overall
03300	moments in various  positions  and  orientations.   Display  requires
03400	description  of  surface properties and two dimensional proximity, to
03500	find overlapping surfaces in the image. Recognition  requires  visual
03600	memory  for  generation  of  hypotheses,  prediction and verification
03700	facilities, geometric relations among parts, and  a  good  choice  of
03800	parts.
03900	
04000	The  representations  [Binford  1971]  depend  upon  segmentation  of
04100	complex objects into parts.  Parts  can  themselves  be  composed  of
04200	subparts.   The  value  of  the  part/whole segmentation depends on a
04300	useful representation for primitive parts.    The  basic  topological
04400	operations  of  cutting  and  pasting are used in joining parts.  The
04500	representation of parts and  joints  amounts  to  the  basis  for  an
04600	intelligent guess about structure. Special knowledge about joints, eg
04700	the anatomy of humans, is much more powerful.
04800	
04900	Primitive parts  are  described  by  volume  representations.     The
05000	primitive   parts   are   arm-like  pieces  which  are  described  as
05100	"generalized   local   cones"   by   localizing   and    generalizing
05200	translational  invariance  [Binford 1971].  These local cones are the
05300	volumes  swept  out  by  translating  an  arbitrary  cross   section,
05400	maintaining it normal to the path along which it is translated, while
05500	the scale of the cross section is changed smoothly.  More  generally,
05600	we  have locally snake-like and locally screw-like shapes.  The basis
05700	of this representation is transformation of local descriptions.   The
05800	typical  element is a snake-like piece described by an axis (which is
05900	a space curve) and arbitrary normal cross-section valued functions.